package arithmetic2.day02;

import java.util.Arrays;

/*
    快速排序
 */
public class Demo05 {
    public static void main(String[] args) {
        int arr[] = new int[]{3,6,8,3,1,2,0};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int arr[], int start, int end) {
        if (start < end) {
            //随机选取一个划分标准
            int temp = arr[start + (int) (Math.random() * (end - start + 1))];
            //将数组划分
            int res[] = partition(arr, start, end, temp);
            //左边继续排序
            quickSort(arr, start, res[0]);
            //右边继续排序
            quickSort(arr, res[1], end);
        }
    }

    //划分
    public static int[] partition(int arr[], int start, int end, int temp) {
        int res[] = new int[2];
        //小于区域最大索引
        int i = start - 1;
        //大于区域最小索引
        int j = end + 1;
        //遍历数组,将数组划分好
        for (int k = start; k <=end && j>k; k++) {
            if (arr[k] < temp) {    //当前数小于temp,将当前数与小于区域的后一个数交换，将小于区域右扩
                swap(arr,k,i+1);
                i++;
            }else if(arr[k] > temp){ //当前数大于temp，将当前数与大于区域的前一个数交换，将大于区域左扩,k不变
                swap(arr,k,j-1);
                j--;
                k--;
            }
        }
        res[0] = i;
        res[1] = j;
        return res;
    }

    //交换两个数
    public static void swap(int arr[], int i, int j) {
        int temp =  arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
